package com.fang.algorithm.zuo.linked;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 两个链表相加
 * 1->2->3->4
 * 2->3->4
 * 得到
 * 1->2->2->3->3->4->4
 * @date 2022/4/23 12:28 上午
 **/
public class Test08_MergeTwoSortLinkedList {

    public static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);
        node1.next.next.next = new Node(4);
        Node node2 = new Node(2);
        node2.next = new Node(3);
        node2.next.next = new Node(4);
        printNode(node1);
        printNode(node2);
        Node addNode = mergeTwoLinkedList(node1, node2);
        printNode(addNode);
    }

    private static Node mergeTwoLinkedList(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        Node head = head1.value <= head2.value ? head1 : head2;
        Node curr1 = head.next;
        Node curr2 = head == head1 ? head2 : head1;
        Node pre = head;
        while (curr1 != null && curr2 != null) {
            if (curr1.value > curr2.value) {
                pre.next = curr2;
                curr2 = curr2.next;
            } else {
                pre.next = curr1;
                curr1 = curr1.next;
            }
            pre = pre.next;
        }
        // 当有一个为空时跳出训话head没有处理完另一个node
        pre.next = curr1 == null ? curr2 : curr1;
        return head;
    }


    private static void printNode(Node reverseNode) {
        while (reverseNode != null) {
            System.out.print(reverseNode.value + "->");
            reverseNode = reverseNode.next;
        }
        System.out.println();
    }
}
